<html>
  <head>
  <title>gridworld.py</title>
  </head>
  <body>
  <h3>gridworld.py (<a href="../gridworld.py">original</a>)</h3>
  <hr>
  <pre>
<span style="color: green; font-style: italic"># gridworld.py
# ------------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

</span><span style="color: blue; font-weight: bold">import </span>random
<span style="color: blue; font-weight: bold">import </span>sys
<span style="color: blue; font-weight: bold">import </span>mdp
<span style="color: blue; font-weight: bold">import </span>environment
<span style="color: blue; font-weight: bold">import </span>util
<span style="color: blue; font-weight: bold">import </span>optparse

<span style="color: blue; font-weight: bold">class </span>Gridworld<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">.</span>MarkovDecisionProcess<span style="font-weight: bold">):
  </span><span style="color: darkred">"""
    Gridworld
  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>grid<span style="font-weight: bold">):
    </span><span style="color: green; font-style: italic"># layout
    </span><span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">) == </span>type<span style="font-weight: bold">([]): </span>grid <span style="font-weight: bold">= </span>makeGrid<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid <span style="font-weight: bold">= </span>grid
    
    <span style="color: green; font-style: italic"># parameters
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>livingReward <span style="font-weight: bold">= </span><span style="color: red">0.0
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise <span style="font-weight: bold">= </span><span style="color: red">0.2
        
  </span><span style="color: blue; font-weight: bold">def </span>setLivingReward<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>reward<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    The (negative) reward for exiting "normal" states.
    
    Note that in the R+N text, this reward is on entering
    a state and therefore is not clearly part of the state's
    future rewards.
    """
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>livingReward <span style="font-weight: bold">= </span>reward
        
  <span style="color: blue; font-weight: bold">def </span>setNoise<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>noise<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    The probability of moving in an unintended direction.
    """
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise <span style="font-weight: bold">= </span>noise
        
                                    
  <span style="color: blue; font-weight: bold">def </span>getPossibleActions<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Returns list of valid actions for 'state'.
    
    Note that you can request moves into walls and
    that "exit" states transition to the terminal
    state under the special action "done".
    """
    </span><span style="color: blue; font-weight: bold">if </span>state <span style="font-weight: bold">== </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>terminalState<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">()
    </span>x<span style="font-weight: bold">,</span>y <span style="font-weight: bold">= </span>state
    <span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">]) == </span>int<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span><span style="color: red">'exit'</span><span style="font-weight: bold">,)
    </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span><span style="color: red">'north'</span><span style="font-weight: bold">,</span><span style="color: red">'west'</span><span style="font-weight: bold">,</span><span style="color: red">'south'</span><span style="font-weight: bold">,</span><span style="color: red">'east'</span><span style="font-weight: bold">)
    
  </span><span style="color: blue; font-weight: bold">def </span>getStates<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Return list of all states.
    """
    </span><span style="color: green; font-style: italic"># The true terminal state.
    </span>states <span style="font-weight: bold">= [</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>terminalState<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>width<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>height<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] != </span><span style="color: red">'#'</span><span style="font-weight: bold">:
          </span>state <span style="font-weight: bold">= (</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">)
          </span>states<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">return </span>states
        
  <span style="color: blue; font-weight: bold">def </span>getReward<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">, </span>nextState<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Get reward for state, action, nextState transition.
    
    Note that the reward depends only on the state being
    departed (as in the R+N book examples, which more or
    less use this convention).
    """
    </span><span style="color: blue; font-weight: bold">if </span>state <span style="font-weight: bold">== </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>terminalState<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0.0
    </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>state
    cell <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span>cell<span style="font-weight: bold">) == </span>int <span style="color: blue; font-weight: bold">or </span>type<span style="font-weight: bold">(</span>cell<span style="font-weight: bold">) == </span>float<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>cell
    <span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>livingReward
        
  <span style="color: blue; font-weight: bold">def </span>getStartState<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>width<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>height<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] == </span><span style="color: red">'S'</span><span style="font-weight: bold">:
          </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span>x<span style="font-weight: bold">, </span>y<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">'Grid has no start state'
    
  </span><span style="color: blue; font-weight: bold">def </span>isTerminal<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Only the TERMINAL_STATE state is *actually* a terminal state.
    The other "exit" states are technically non-terminals with
    a single action "exit" which leads to the true terminal state.
    This convention is to make the grids line up with the examples
    in the R+N textbook.
    """
    </span><span style="color: blue; font-weight: bold">return </span>state <span style="font-weight: bold">== </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>terminalState
        
                   
  <span style="color: blue; font-weight: bold">def </span>getTransitionStatesAndProbs<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Returns list of (nextState, prob) pairs
    representing the states reachable
    from 'state' by taking 'action' along
    with their transition probabilities.          
    """        
        
    </span><span style="color: blue; font-weight: bold">if </span>action <span style="color: blue; font-weight: bold">not in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">(</span>state<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">"Illegal action!"
      
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>isTerminal<span style="font-weight: bold">(</span>state<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">[]
    
    </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>state
    
    <span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">]) == </span>int <span style="color: blue; font-weight: bold">or </span>type<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">]) == </span>float<span style="font-weight: bold">:
      </span>termState <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>terminalState
      <span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">[(</span>termState<span style="font-weight: bold">, </span><span style="color: red">1.0</span><span style="font-weight: bold">)]
      
    </span>successors <span style="font-weight: bold">= []                
                
    </span>northState <span style="font-weight: bold">= (</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__isAllowed<span style="font-weight: bold">(</span>y<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">,</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">)) </span><span style="color: blue; font-weight: bold">or </span>state
    westState <span style="font-weight: bold">= (</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__isAllowed<span style="font-weight: bold">(</span>y<span style="font-weight: bold">,</span>x<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>x<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">)) </span><span style="color: blue; font-weight: bold">or </span>state
    southState <span style="font-weight: bold">= (</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__isAllowed<span style="font-weight: bold">(</span>y<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">,</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">-</span><span style="color: red">1</span><span style="font-weight: bold">)) </span><span style="color: blue; font-weight: bold">or </span>state
    eastState <span style="font-weight: bold">= (</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__isAllowed<span style="font-weight: bold">(</span>y<span style="font-weight: bold">,</span>x<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span><span style="font-weight: bold">(</span>x<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">,</span>y<span style="font-weight: bold">)) </span><span style="color: blue; font-weight: bold">or </span>state
                        
    <span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: red">'north' </span><span style="color: blue; font-weight: bold">or </span>action <span style="font-weight: bold">== </span><span style="color: red">'south'</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: red">'north'</span><span style="font-weight: bold">: 
        </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>northState<span style="font-weight: bold">,</span><span style="color: red">1</span><span style="font-weight: bold">-</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise<span style="font-weight: bold">))
      </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
        </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>southState<span style="font-weight: bold">,</span><span style="color: red">1</span><span style="font-weight: bold">-</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise<span style="font-weight: bold">))
                                
      </span>massLeft <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise
      successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>westState<span style="font-weight: bold">,</span>massLeft<span style="font-weight: bold">/</span><span style="color: red">2.0</span><span style="font-weight: bold">))    
      </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>eastState<span style="font-weight: bold">,</span>massLeft<span style="font-weight: bold">/</span><span style="color: red">2.0</span><span style="font-weight: bold">))
                                
    </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: red">'west' </span><span style="color: blue; font-weight: bold">or </span>action <span style="font-weight: bold">== </span><span style="color: red">'east'</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: red">'west'</span><span style="font-weight: bold">:
        </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>westState<span style="font-weight: bold">,</span><span style="color: red">1</span><span style="font-weight: bold">-</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise<span style="font-weight: bold">))
      </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
        </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>eastState<span style="font-weight: bold">,</span><span style="color: red">1</span><span style="font-weight: bold">-</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise<span style="font-weight: bold">))
                
      </span>massLeft <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>noise
      successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>northState<span style="font-weight: bold">,</span>massLeft<span style="font-weight: bold">/</span><span style="color: red">2.0</span><span style="font-weight: bold">))
      </span>successors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>southState<span style="font-weight: bold">,</span>massLeft<span style="font-weight: bold">/</span><span style="color: red">2.0</span><span style="font-weight: bold">)) 
      
    </span>successors <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>__aggregate<span style="font-weight: bold">(</span>successors<span style="font-weight: bold">)
                                                                           
    </span><span style="color: blue; font-weight: bold">return </span>successors                                
  
  <span style="color: blue; font-weight: bold">def </span>__aggregate<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>statesAndProbs<span style="font-weight: bold">):
    </span>counter <span style="font-weight: bold">= </span>util<span style="font-weight: bold">.</span>Counter<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">for </span>state<span style="font-weight: bold">, </span>prob <span style="color: blue; font-weight: bold">in </span>statesAndProbs<span style="font-weight: bold">:
      </span>counter<span style="font-weight: bold">[</span>state<span style="font-weight: bold">] += </span>prob
    newStatesAndProbs <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>state<span style="font-weight: bold">, </span>prob <span style="color: blue; font-weight: bold">in </span>counter<span style="font-weight: bold">.</span>items<span style="font-weight: bold">():
      </span>newStatesAndProbs<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>state<span style="font-weight: bold">, </span>prob<span style="font-weight: bold">))
    </span><span style="color: blue; font-weight: bold">return </span>newStatesAndProbs
        
  <span style="color: blue; font-weight: bold">def </span>__isAllowed<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>y<span style="font-weight: bold">, </span>x<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>y <span style="font-weight: bold">&lt; </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">or </span>y <span style="font-weight: bold">&gt;= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>height<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    if </span>x <span style="font-weight: bold">&lt; </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">or </span>x <span style="font-weight: bold">&gt;= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">.</span>width<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] != </span><span style="color: red">'#'

</span><span style="color: blue; font-weight: bold">class </span>GridworldEnvironment<span style="font-weight: bold">(</span>environment<span style="font-weight: bold">.</span>Environment<span style="font-weight: bold">):
    
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>gridWorld<span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gridWorld <span style="font-weight: bold">= </span>gridWorld
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>reset<span style="font-weight: bold">()
            
  </span><span style="color: blue; font-weight: bold">def </span>getCurrentState<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state
        
  <span style="color: blue; font-weight: bold">def </span>getPossibleActions<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):        
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gridWorld<span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
        
  </span><span style="color: blue; font-weight: bold">def </span>doAction<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>action<span style="font-weight: bold">):
    </span>successors <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gridWorld<span style="font-weight: bold">.</span>getTransitionStatesAndProbs<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">) 
    </span>sum <span style="font-weight: bold">= </span><span style="color: red">0.0
    </span>rand <span style="font-weight: bold">= </span>random<span style="font-weight: bold">.</span>random<span style="font-weight: bold">()
    </span>state <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>getCurrentState<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">for </span>nextState<span style="font-weight: bold">, </span>prob <span style="color: blue; font-weight: bold">in </span>successors<span style="font-weight: bold">:
      </span>sum <span style="font-weight: bold">+= </span>prob
      <span style="color: blue; font-weight: bold">if </span>sum <span style="font-weight: bold">&gt; </span><span style="color: red">1.0</span><span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">'Total transition probability more than one; sample failure.' 
      </span><span style="color: blue; font-weight: bold">if </span>rand <span style="font-weight: bold">&lt; </span>sum<span style="font-weight: bold">:
        </span>reward <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gridWorld<span style="font-weight: bold">.</span>getReward<span style="font-weight: bold">(</span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">, </span>nextState<span style="font-weight: bold">)
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state <span style="font-weight: bold">= </span>nextState
        <span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span>nextState<span style="font-weight: bold">, </span>reward<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">'Total transition probability less than one; sample failure.'    
        
  </span><span style="color: blue; font-weight: bold">def </span>reset<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gridWorld<span style="font-weight: bold">.</span>getStartState<span style="font-weight: bold">()

</span><span style="color: blue; font-weight: bold">class </span>Grid<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  A 2-dimensional array of immutables backed by a list of lists.  Data is accessed
  via grid[x][y] where (x,y) are cartesian coordinates with x horizontal,
  y vertical and the origin (0,0) in the bottom left corner.  
  
  The __str__ method constructs an output that is oriented appropriately.
  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>width<span style="font-weight: bold">, </span>height<span style="font-weight: bold">, </span>initialValue<span style="font-weight: bold">=</span><span style="color: red">' '</span><span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width <span style="font-weight: bold">= </span>width
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>height <span style="font-weight: bold">= </span>height
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>data <span style="font-weight: bold">= [[</span>initialValue <span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>height<span style="font-weight: bold">)] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>width<span style="font-weight: bold">)]
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>terminalState <span style="font-weight: bold">= </span><span style="color: red">'TERMINAL_STATE'
    
  </span><span style="color: blue; font-weight: bold">def </span>__getitem__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>i<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>i<span style="font-weight: bold">]
  
  </span><span style="color: blue; font-weight: bold">def </span>__setitem__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>key<span style="font-weight: bold">, </span>item<span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>key<span style="font-weight: bold">] = </span>item
    
  <span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>other <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>data
    
  <span style="color: blue; font-weight: bold">def </span>__hash__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">)
  
  </span><span style="color: blue; font-weight: bold">def </span>copy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>g <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)
    </span>g<span style="font-weight: bold">.</span>data <span style="font-weight: bold">= [</span>x<span style="font-weight: bold">[:] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">return </span>g
  
  <span style="color: blue; font-weight: bold">def </span>deepCopy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>copy<span style="font-weight: bold">()
  
  </span><span style="color: blue; font-weight: bold">def </span>shallowCopy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>g <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)
    </span>g<span style="font-weight: bold">.</span>data <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data
    <span style="color: blue; font-weight: bold">return </span>g
    
  <span style="color: blue; font-weight: bold">def </span>_getLegacyText<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>t <span style="font-weight: bold">= [[</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">)] </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)]
    </span>t<span style="font-weight: bold">.</span>reverse<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">return </span>t
    
  <span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>str<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_getLegacyText<span style="font-weight: bold">())

</span><span style="color: blue; font-weight: bold">def </span>makeGrid<span style="font-weight: bold">(</span>gridString<span style="font-weight: bold">):
  </span>width<span style="font-weight: bold">, </span>height <span style="font-weight: bold">= </span>len<span style="font-weight: bold">(</span>gridString<span style="font-weight: bold">[</span><span style="color: red">0</span><span style="font-weight: bold">]), </span>len<span style="font-weight: bold">(</span>gridString<span style="font-weight: bold">)
  </span>grid <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span>width<span style="font-weight: bold">, </span>height<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">for </span>ybar<span style="font-weight: bold">, </span>line <span style="color: blue; font-weight: bold">in </span>enumerate<span style="font-weight: bold">(</span>gridString<span style="font-weight: bold">):
    </span>y <span style="font-weight: bold">= </span>height <span style="font-weight: bold">- </span>ybar <span style="font-weight: bold">- </span><span style="color: red">1
    </span><span style="color: blue; font-weight: bold">for </span>x<span style="font-weight: bold">, </span>el <span style="color: blue; font-weight: bold">in </span>enumerate<span style="font-weight: bold">(</span>line<span style="font-weight: bold">):
      </span>grid<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span>el
  <span style="color: blue; font-weight: bold">return </span>grid    
             
<span style="color: blue; font-weight: bold">def </span>getCliffGrid<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">'S'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">10</span><span style="font-weight: bold">],
          [-</span><span style="color: red">100</span><span style="font-weight: bold">,-</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>makeGrid<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">))
    
</span><span style="color: blue; font-weight: bold">def </span>getCliffGrid2<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">8</span><span style="font-weight: bold">,</span><span style="color: red">'S'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">10</span><span style="font-weight: bold">],
          [-</span><span style="color: red">100</span><span style="font-weight: bold">,-</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)
    
</span><span style="color: blue; font-weight: bold">def </span>getDiscountGrid<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">, </span><span style="color: red">10</span><span style="font-weight: bold">],
          [</span><span style="color: red">'S'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [-</span><span style="color: red">10</span><span style="font-weight: bold">,-</span><span style="color: red">10</span><span style="font-weight: bold">, -</span><span style="color: red">10</span><span style="font-weight: bold">, -</span><span style="color: red">10</span><span style="font-weight: bold">, -</span><span style="color: red">10</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)
   
</span><span style="color: blue; font-weight: bold">def </span>getBridgeGrid<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[ </span><span style="color: red">'#'</span><span style="font-weight: bold">,-</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, </span><span style="color: red">'#'</span><span style="font-weight: bold">],
          [   </span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">'S'</span><span style="font-weight: bold">,  </span><span style="color: red">' '</span><span style="font-weight: bold">,  </span><span style="color: red">' '</span><span style="font-weight: bold">,  </span><span style="color: red">' '</span><span style="font-weight: bold">,  </span><span style="color: red">' '</span><span style="font-weight: bold">,  </span><span style="color: red">10</span><span style="font-weight: bold">],
          [ </span><span style="color: red">'#'</span><span style="font-weight: bold">,-</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, -</span><span style="color: red">100</span><span style="font-weight: bold">, </span><span style="color: red">'#'</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">def </span>getBookGrid<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,+</span><span style="color: red">1</span><span style="font-weight: bold">],
          [</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,-</span><span style="color: red">1</span><span style="font-weight: bold">],
          [</span><span style="color: red">'S'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">def </span>getMazeGrid<span style="font-weight: bold">():
  </span>grid <span style="font-weight: bold">= [[</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,+</span><span style="color: red">1</span><span style="font-weight: bold">],
          [</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">],
          [</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">'#'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">],
          [</span><span style="color: red">'S'</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">,</span><span style="color: red">' '</span><span style="font-weight: bold">]]
  </span><span style="color: blue; font-weight: bold">return </span>Gridworld<span style="font-weight: bold">(</span>grid<span style="font-weight: bold">)



</span><span style="color: blue; font-weight: bold">def </span>getUserAction<span style="font-weight: bold">(</span>state<span style="font-weight: bold">, </span>actionFunction<span style="font-weight: bold">):
  </span><span style="color: darkred">"""
  Get an action from the user (rather than the agent).
  
  Used for debugging and lecture demos.
  """
  </span><span style="color: blue; font-weight: bold">import </span>graphicsUtils
  action <span style="font-weight: bold">= </span><span style="color: blue">None
  </span><span style="color: blue; font-weight: bold">while True</span><span style="font-weight: bold">:
    </span>keys <span style="font-weight: bold">= </span>graphicsUtils<span style="font-weight: bold">.</span>wait_for_keys<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'Up' </span><span style="color: blue; font-weight: bold">in </span>keys<span style="font-weight: bold">: </span>action <span style="font-weight: bold">= </span><span style="color: red">'north'
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'Down' </span><span style="color: blue; font-weight: bold">in </span>keys<span style="font-weight: bold">: </span>action <span style="font-weight: bold">= </span><span style="color: red">'south'
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'Left' </span><span style="color: blue; font-weight: bold">in </span>keys<span style="font-weight: bold">: </span>action <span style="font-weight: bold">= </span><span style="color: red">'west'
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'Right' </span><span style="color: blue; font-weight: bold">in </span>keys<span style="font-weight: bold">: </span>action <span style="font-weight: bold">= </span><span style="color: red">'east'
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'q' </span><span style="color: blue; font-weight: bold">in </span>keys<span style="font-weight: bold">: </span>sys<span style="font-weight: bold">.</span>exit<span style="font-weight: bold">(</span><span style="color: red">0</span><span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
    break
  </span>actions <span style="font-weight: bold">= </span>actionFunction<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">if </span>action <span style="color: blue; font-weight: bold">not in </span>actions<span style="font-weight: bold">:
    </span>action <span style="font-weight: bold">= </span>actions<span style="font-weight: bold">[</span><span style="color: red">0</span><span style="font-weight: bold">]
  </span><span style="color: blue; font-weight: bold">return </span>action

<span style="color: blue; font-weight: bold">def </span>printString<span style="font-weight: bold">(</span>x<span style="font-weight: bold">): </span><span style="color: blue; font-weight: bold">print </span>x

<span style="color: blue; font-weight: bold">def </span>runEpisode<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">, </span>environment<span style="font-weight: bold">, </span>discount<span style="font-weight: bold">, </span>decision<span style="font-weight: bold">, </span>display<span style="font-weight: bold">, </span>message<span style="font-weight: bold">, </span>pause<span style="font-weight: bold">, </span>episode<span style="font-weight: bold">):
  </span>returns <span style="font-weight: bold">= </span><span style="color: red">0
  </span>totalDiscount <span style="font-weight: bold">= </span><span style="color: red">1.0
  </span>environment<span style="font-weight: bold">.</span>reset<span style="font-weight: bold">()
  </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'startEpisode' </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">): </span>agent<span style="font-weight: bold">.</span>startEpisode<span style="font-weight: bold">()
  </span>message<span style="font-weight: bold">(</span><span style="color: red">"BEGINNING EPISODE: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>episode<span style="font-weight: bold">)+</span><span style="color: red">"\n"</span><span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">while True</span><span style="font-weight: bold">:

    </span><span style="color: green; font-style: italic"># DISPLAY CURRENT STATE
    </span>state <span style="font-weight: bold">= </span>environment<span style="font-weight: bold">.</span>getCurrentState<span style="font-weight: bold">()
    </span>display<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span>pause<span style="font-weight: bold">()
    
    </span><span style="color: green; font-style: italic"># END IF IN A TERMINAL STATE
    </span>actions <span style="font-weight: bold">= </span>environment<span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>len<span style="font-weight: bold">(</span>actions<span style="font-weight: bold">) == </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span>message<span style="font-weight: bold">(</span><span style="color: red">"EPISODE "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>episode<span style="font-weight: bold">)+</span><span style="color: red">" COMPLETE: RETURN WAS "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>returns<span style="font-weight: bold">)+</span><span style="color: red">"\n"</span><span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">return </span>returns
    
    <span style="color: green; font-style: italic"># GET ACTION (USUALLY FROM AGENT)
    </span>action <span style="font-weight: bold">= </span>decision<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">'Error: Agent returned None action'
    
    </span><span style="color: green; font-style: italic"># EXECUTE ACTION
    </span>nextState<span style="font-weight: bold">, </span>reward <span style="font-weight: bold">= </span>environment<span style="font-weight: bold">.</span>doAction<span style="font-weight: bold">(</span>action<span style="font-weight: bold">)
    </span>message<span style="font-weight: bold">(</span><span style="color: red">"Started in state: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)+
            </span><span style="color: red">"\nTook action: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>action<span style="font-weight: bold">)+
            </span><span style="color: red">"\nEnded in state: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>nextState<span style="font-weight: bold">)+
            </span><span style="color: red">"\nGot reward: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>reward<span style="font-weight: bold">)+</span><span style="color: red">"\n"</span><span style="font-weight: bold">)    
    </span><span style="color: green; font-style: italic"># UPDATE LEARNER
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'observeTransition' </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">): 
        </span>agent<span style="font-weight: bold">.</span>observeTransition<span style="font-weight: bold">(</span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">, </span>nextState<span style="font-weight: bold">, </span>reward<span style="font-weight: bold">)
    
    </span>returns <span style="font-weight: bold">+= </span>reward <span style="font-weight: bold">* </span>totalDiscount
    totalDiscount <span style="font-weight: bold">*= </span>discount

  <span style="color: blue; font-weight: bold">if </span><span style="color: red">'stopEpisode' </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">):
    </span>agent<span style="font-weight: bold">.</span>stopEpisode<span style="font-weight: bold">()

</span><span style="color: blue; font-weight: bold">def </span>parseOptions<span style="font-weight: bold">():
    </span>optParser <span style="font-weight: bold">= </span>optparse<span style="font-weight: bold">.</span>OptionParser<span style="font-weight: bold">()
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-d'</span><span style="font-weight: bold">, </span><span style="color: red">'--discount'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'float'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'discount'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">0.9</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Discount on future (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-r'</span><span style="font-weight: bold">, </span><span style="color: red">'--livingReward'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'float'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'livingReward'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">0.0</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"R"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'Reward for living for a time step (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-n'</span><span style="font-weight: bold">, </span><span style="color: red">'--noise'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'float'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'noise'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">0.2</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"P"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'How often action results in ' </span><span style="font-weight: bold">+
                         </span><span style="color: red">'unintended direction (default %default)' </span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-e'</span><span style="font-weight: bold">, </span><span style="color: red">'--epsilon'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'float'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'epsilon'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">0.3</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"E"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'Chance of taking a random action in q-learning (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-l'</span><span style="font-weight: bold">, </span><span style="color: red">'--learningRate'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'float'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'learningRate'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">0.5</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"P"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'TD learning rate (default %default)' </span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-i'</span><span style="font-weight: bold">, </span><span style="color: red">'--iterations'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'int'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'iters'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">10</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"K"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'Number of rounds of value iteration (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-k'</span><span style="font-weight: bold">, </span><span style="color: red">'--episodes'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'int'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'episodes'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">1</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"K"</span><span style="font-weight: bold">, </span>help<span style="font-weight: bold">=</span><span style="color: red">'Number of epsiodes of the MDP to run (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-g'</span><span style="font-weight: bold">, </span><span style="color: red">'--grid'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">,
                         </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"G"</span><span style="font-weight: bold">, </span>type<span style="font-weight: bold">=</span><span style="color: red">'string'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'grid'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">"BookGrid"</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Grid to use (case sensitive; options are BookGrid, BridgeGrid, CliffGrid, MazeGrid, default %default)' </span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-w'</span><span style="font-weight: bold">, </span><span style="color: red">'--windowSize'</span><span style="font-weight: bold">, </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"X"</span><span style="font-weight: bold">, </span>type<span style="font-weight: bold">=</span><span style="color: red">'int'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'gridSize'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">150</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Request a window width of X pixels *per grid cell* (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-a'</span><span style="font-weight: bold">, </span><span style="color: red">'--agent'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">, </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"A"</span><span style="font-weight: bold">,
                         </span>type<span style="font-weight: bold">=</span><span style="color: red">'string'</span><span style="font-weight: bold">,</span>dest<span style="font-weight: bold">=</span><span style="color: red">'agent'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">"random"</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Agent type (options are \'random\', \'value\' and \'q\', default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-t'</span><span style="font-weight: bold">, </span><span style="color: red">'--text'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store_true'</span><span style="font-weight: bold">,
                         </span>dest<span style="font-weight: bold">=</span><span style="color: red">'textDisplay'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Use text-only ASCII display'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-p'</span><span style="font-weight: bold">, </span><span style="color: red">'--pause'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store_true'</span><span style="font-weight: bold">,
                         </span>dest<span style="font-weight: bold">=</span><span style="color: red">'pause'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Pause GUI after each time step when running the MDP'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-q'</span><span style="font-weight: bold">, </span><span style="color: red">'--quiet'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store_true'</span><span style="font-weight: bold">,
                         </span>dest<span style="font-weight: bold">=</span><span style="color: red">'quiet'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Skip display of any learning episodes'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-s'</span><span style="font-weight: bold">, </span><span style="color: red">'--speed'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store'</span><span style="font-weight: bold">, </span>metavar<span style="font-weight: bold">=</span><span style="color: red">"S"</span><span style="font-weight: bold">, </span>type<span style="font-weight: bold">=</span>float<span style="font-weight: bold">,
                         </span>dest<span style="font-weight: bold">=</span><span style="color: red">'speed'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: red">1.0</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Speed of animation, S &gt; 1.0 is faster, 0.0 &lt; S &lt; 1.0 is slower (default %default)'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-m'</span><span style="font-weight: bold">, </span><span style="color: red">'--manual'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store_true'</span><span style="font-weight: bold">,
                         </span>dest<span style="font-weight: bold">=</span><span style="color: red">'manual'</span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Manually control agent'</span><span style="font-weight: bold">)
    </span>optParser<span style="font-weight: bold">.</span>add_option<span style="font-weight: bold">(</span><span style="color: red">'-v'</span><span style="font-weight: bold">, </span><span style="color: red">'--valueSteps'</span><span style="font-weight: bold">,</span>action<span style="font-weight: bold">=</span><span style="color: red">'store_true' </span><span style="font-weight: bold">,</span>default<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">,
                         </span>help<span style="font-weight: bold">=</span><span style="color: red">'Display each step of value iteration'</span><span style="font-weight: bold">)

    </span>opts<span style="font-weight: bold">, </span>args <span style="font-weight: bold">= </span>optParser<span style="font-weight: bold">.</span>parse_args<span style="font-weight: bold">()
    
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>manual <span style="color: blue; font-weight: bold">and </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">!= </span><span style="color: red">'q'</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">'## Disabling Agents in Manual Mode (-m) ##'
      </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">= </span><span style="color: blue">None

    </span><span style="color: green; font-style: italic"># MANAGE CONFLICTS
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>textDisplay <span style="color: blue; font-weight: bold">or </span>opts<span style="font-weight: bold">.</span>quiet<span style="font-weight: bold">:
    </span><span style="color: green; font-style: italic"># if opts.quiet:      
      </span>opts<span style="font-weight: bold">.</span>pause <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
      </span><span style="color: green; font-style: italic"># opts.manual = False
      
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>manual<span style="font-weight: bold">:
      </span>opts<span style="font-weight: bold">.</span>pause <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
      
    return </span>opts

  
<span style="color: blue; font-weight: bold">if </span>__name__ <span style="font-weight: bold">== </span><span style="color: red">'__main__'</span><span style="font-weight: bold">:
  
  </span>opts <span style="font-weight: bold">= </span>parseOptions<span style="font-weight: bold">()

  </span><span style="color: green; font-style: italic">###########################
  # GET THE GRIDWORLD
  ###########################

  </span><span style="color: blue; font-weight: bold">import </span>gridworld
  mdpFunction <span style="font-weight: bold">= </span>getattr<span style="font-weight: bold">(</span>gridworld<span style="font-weight: bold">, </span><span style="color: red">"get"</span><span style="font-weight: bold">+</span>opts<span style="font-weight: bold">.</span>grid<span style="font-weight: bold">)
  </span>mdp <span style="font-weight: bold">= </span>mdpFunction<span style="font-weight: bold">()
  </span>mdp<span style="font-weight: bold">.</span>setLivingReward<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>livingReward<span style="font-weight: bold">)
  </span>mdp<span style="font-weight: bold">.</span>setNoise<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>noise<span style="font-weight: bold">)
  </span>env <span style="font-weight: bold">= </span>gridworld<span style="font-weight: bold">.</span>GridworldEnvironment<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">)

  
  </span><span style="color: green; font-style: italic">###########################
  # GET THE DISPLAY ADAPTER
  ###########################

  </span><span style="color: blue; font-weight: bold">import </span>textGridworldDisplay
  display <span style="font-weight: bold">= </span>textGridworldDisplay<span style="font-weight: bold">.</span>TextGridworldDisplay<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">if not </span>opts<span style="font-weight: bold">.</span>textDisplay<span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">import </span>graphicsGridworldDisplay
    display <span style="font-weight: bold">= </span>graphicsGridworldDisplay<span style="font-weight: bold">.</span>GraphicsGridworldDisplay<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>gridSize<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>speed<span style="font-weight: bold">)
  </span>display<span style="font-weight: bold">.</span>start<span style="font-weight: bold">()

  </span><span style="color: green; font-style: italic">###########################
  # GET THE AGENT
  ###########################

  </span><span style="color: blue; font-weight: bold">import </span>valueIterationAgents<span style="font-weight: bold">, </span>qlearningAgents
  a <span style="font-weight: bold">= </span><span style="color: blue">None
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'value'</span><span style="font-weight: bold">:
    </span>a <span style="font-weight: bold">= </span>valueIterationAgents<span style="font-weight: bold">.</span>ValueIterationAgent<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>discount<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>iters<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">elif </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'q'</span><span style="font-weight: bold">:
    </span><span style="color: green; font-style: italic">#env.getPossibleActions, opts.discount, opts.learningRate, opts.epsilon
    #simulationFn = lambda agent, state: simulation.GridworldSimulation(agent,state,mdp)
    </span>gridWorldEnv <span style="font-weight: bold">= </span>GridworldEnvironment<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">)
    </span>actionFn <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state<span style="font-weight: bold">: </span>mdp<span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span>qLearnOpts <span style="font-weight: bold">= {</span><span style="color: red">'gamma'</span><span style="font-weight: bold">: </span>opts<span style="font-weight: bold">.</span>discount<span style="font-weight: bold">, 
                  </span><span style="color: red">'alpha'</span><span style="font-weight: bold">: </span>opts<span style="font-weight: bold">.</span>learningRate<span style="font-weight: bold">, 
                  </span><span style="color: red">'epsilon'</span><span style="font-weight: bold">: </span>opts<span style="font-weight: bold">.</span>epsilon<span style="font-weight: bold">,
                  </span><span style="color: red">'actionFn'</span><span style="font-weight: bold">: </span>actionFn<span style="font-weight: bold">}
    </span>a <span style="font-weight: bold">= </span>qlearningAgents<span style="font-weight: bold">.</span>QLearningAgent<span style="font-weight: bold">(**</span>qLearnOpts<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">elif </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'random'</span><span style="font-weight: bold">:
    </span><span style="color: green; font-style: italic"># # No reason to use the random agent without episodes
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>episodes <span style="font-weight: bold">== </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span>opts<span style="font-weight: bold">.</span>episodes <span style="font-weight: bold">= </span><span style="color: red">10
    </span><span style="color: blue; font-weight: bold">class </span>RandomAgent<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">def </span>getAction<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">return </span>random<span style="font-weight: bold">.</span>choice<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">(</span>state<span style="font-weight: bold">))
      </span><span style="color: blue; font-weight: bold">def </span>getValue<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0.0
      </span><span style="color: blue; font-weight: bold">def </span>getQValue<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">0.0
      </span><span style="color: blue; font-weight: bold">def </span>getPolicy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
        </span><span style="color: red">"NOTE: 'random' is a special policy value; don't use it in your code."
        </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'random'
      </span><span style="color: blue; font-weight: bold">def </span>update<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span>action<span style="font-weight: bold">, </span>nextState<span style="font-weight: bold">, </span>reward<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">pass      
    </span>a <span style="font-weight: bold">= </span>RandomAgent<span style="font-weight: bold">()
  </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">if not </span>opts<span style="font-weight: bold">.</span>manual<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">raise </span><span style="color: red">'Unknown agent type: '</span><span style="font-weight: bold">+</span>opts<span style="font-weight: bold">.</span>agent
    
    
  <span style="color: green; font-style: italic">###########################
  # RUN EPISODES
  ###########################
  # DISPLAY Q/V VALUES BEFORE SIMULATION OF EPISODES
  </span><span style="color: blue; font-weight: bold">if not </span>opts<span style="font-weight: bold">.</span>manual <span style="color: blue; font-weight: bold">and </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'value'</span><span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>valueSteps<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>iters<span style="font-weight: bold">):
        </span>tempAgent <span style="font-weight: bold">= </span>valueIterationAgents<span style="font-weight: bold">.</span>ValueIterationAgent<span style="font-weight: bold">(</span>mdp<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>discount<span style="font-weight: bold">, </span>i<span style="font-weight: bold">)
        </span>display<span style="font-weight: bold">.</span>displayValues<span style="font-weight: bold">(</span>tempAgent<span style="font-weight: bold">, </span>message <span style="font-weight: bold">= </span><span style="color: red">"VALUES AFTER "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>i<span style="font-weight: bold">)+</span><span style="color: red">" ITERATIONS"</span><span style="font-weight: bold">)
        </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()        
    
    </span>display<span style="font-weight: bold">.</span>displayValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>message <span style="font-weight: bold">= </span><span style="color: red">"VALUES AFTER "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>iters<span style="font-weight: bold">)+</span><span style="color: red">" ITERATIONS"</span><span style="font-weight: bold">)
    </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()
    </span>display<span style="font-weight: bold">.</span>displayQValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>message <span style="font-weight: bold">= </span><span style="color: red">"Q-VALUES AFTER "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>iters<span style="font-weight: bold">)+</span><span style="color: red">" ITERATIONS"</span><span style="font-weight: bold">)
    </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()
    
  

  </span><span style="color: green; font-style: italic"># FIGURE OUT WHAT TO DISPLAY EACH TIME STEP (IF ANYTHING)
  </span>displayCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>x<span style="font-weight: bold">: </span><span style="color: blue">None
  </span><span style="color: blue; font-weight: bold">if not </span>opts<span style="font-weight: bold">.</span>quiet<span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>manual <span style="color: blue; font-weight: bold">and </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: 
      </span>displayCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state<span style="font-weight: bold">: </span>display<span style="font-weight: bold">.</span>displayNullValues<span style="font-weight: bold">(</span>state<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'random'</span><span style="font-weight: bold">: </span>displayCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state<span style="font-weight: bold">: </span>display<span style="font-weight: bold">.</span>displayValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span><span style="color: red">"CURRENT VALUES"</span><span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'value'</span><span style="font-weight: bold">: </span>displayCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state<span style="font-weight: bold">: </span>display<span style="font-weight: bold">.</span>displayValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span><span style="color: red">"CURRENT VALUES"</span><span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'q'</span><span style="font-weight: bold">: </span>displayCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state<span style="font-weight: bold">: </span>display<span style="font-weight: bold">.</span>displayQValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>state<span style="font-weight: bold">, </span><span style="color: red">"CURRENT Q-VALUES"</span><span style="font-weight: bold">)

  </span>messageCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>x<span style="font-weight: bold">: </span>printString<span style="font-weight: bold">(</span>x<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>quiet<span style="font-weight: bold">:
    </span>messageCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>x<span style="font-weight: bold">: </span><span style="color: blue">None

  </span><span style="color: green; font-style: italic"># FIGURE OUT WHETHER TO WAIT FOR A KEY PRESS AFTER EACH TIME STEP
  </span>pauseCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span><span style="font-weight: bold">: </span><span style="color: blue">None
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">:
    </span>pauseCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span><span style="font-weight: bold">: </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()

  </span><span style="color: green; font-style: italic"># FIGURE OUT WHETHER THE USER WANTS MANUAL CONTROL (FOR DEBUGGING AND DEMOS)  
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>manual<span style="font-weight: bold">:
    </span>decisionCallback <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">lambda </span>state <span style="font-weight: bold">: </span>getUserAction<span style="font-weight: bold">(</span>state<span style="font-weight: bold">, </span>mdp<span style="font-weight: bold">.</span>getPossibleActions<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
    </span>decisionCallback <span style="font-weight: bold">= </span>a<span style="font-weight: bold">.</span>getAction  
    
  <span style="color: green; font-style: italic"># RUN EPISODES
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>episodes <span style="font-weight: bold">&gt; </span><span style="color: red">0</span><span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">print
    print </span><span style="color: red">"RUNNING"</span><span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>episodes<span style="font-weight: bold">, </span><span style="color: red">"EPISODES"
    </span><span style="color: blue; font-weight: bold">print
  </span>returns <span style="font-weight: bold">= </span><span style="color: red">0
  </span><span style="color: blue; font-weight: bold">for </span>episode <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: red">1</span><span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>episodes<span style="font-weight: bold">+</span><span style="color: red">1</span><span style="font-weight: bold">):
    </span>returns <span style="font-weight: bold">+= </span>runEpisode<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>env<span style="font-weight: bold">, </span>opts<span style="font-weight: bold">.</span>discount<span style="font-weight: bold">, </span>decisionCallback<span style="font-weight: bold">, </span>displayCallback<span style="font-weight: bold">, </span>messageCallback<span style="font-weight: bold">, </span>pauseCallback<span style="font-weight: bold">, </span>episode<span style="font-weight: bold">)
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>episodes <span style="font-weight: bold">&gt; </span><span style="color: red">0</span><span style="font-weight: bold">:
    </span><span style="color: blue; font-weight: bold">print
    print </span><span style="color: red">"AVERAGE RETURNS FROM START STATE: "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">((</span>returns<span style="font-weight: bold">+</span><span style="color: red">0.0</span><span style="font-weight: bold">) / </span>opts<span style="font-weight: bold">.</span>episodes<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">print
    print
    
  </span><span style="color: green; font-style: italic"># DISPLAY POST-LEARNING VALUES / Q-VALUES
  </span><span style="color: blue; font-weight: bold">if </span>opts<span style="font-weight: bold">.</span>agent <span style="font-weight: bold">== </span><span style="color: red">'q' </span><span style="color: blue; font-weight: bold">and not </span>opts<span style="font-weight: bold">.</span>manual<span style="font-weight: bold">:
    </span>display<span style="font-weight: bold">.</span>displayQValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>message <span style="font-weight: bold">= </span><span style="color: red">"Q-VALUES AFTER "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>episodes<span style="font-weight: bold">)+</span><span style="color: red">" EPISODES"</span><span style="font-weight: bold">)
    </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()
    </span>display<span style="font-weight: bold">.</span>displayValues<span style="font-weight: bold">(</span>a<span style="font-weight: bold">, </span>message <span style="font-weight: bold">= </span><span style="color: red">"VALUES AFTER "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span>opts<span style="font-weight: bold">.</span>episodes<span style="font-weight: bold">)+</span><span style="color: red">" EPISODES"</span><span style="font-weight: bold">)
    </span>display<span style="font-weight: bold">.</span>pause<span style="font-weight: bold">()
    
   </span>
  </pre>
  </body>
  </html>
  